翻訳と辞書 Words near each other ・ Kinetic scheme ・ Kinetic sculpture race ・ Kinetic Securities ・ Kinetic smallest enclosing disk ・ Kinetic sorted list ・ Kinetic Suspension Technology ・ Kinetic term ・ Kinetic theory ・ Kinetic theTechnologyAgency ・ Kinetic tournament ・ Kinetic Traction Systems ・ Kinetic triangulation ・ Kinetic typography ・ Kinetic user interface ・ Kinetic Void ・ Kinetic width ・ Kinetic-segregation model of T cell activation ・ Kinetic.js ・ Kinetica ・ Kinetica (game engine) ・ Kinetica Sports Ltd ・ KineticD ・ KineticGlue ・ KineticNovel ・ Kinetico ・ Kinetics ・ Kinetics & One Love ・ Kinetics (physics) ・ Kinetics (rapper) ・ Kinetics Internet Protocol Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Kinetic width ： ウィキペディア英語版 Kinetic width A kinetic width data structure is a kinetic data structure which maintains the width of a set of moving points. In 2D, the width of a point set is the minimum distance between two parallel lines that contain the point set in the strip between them. For the two dimensional case, the kinetic data structure for kinetic convex hull can be used to construct a kinetic data structure for the width of a point set that is responsive, compact and efficient. ==2D case== Consider the parallel lines which contain the point set in the strip between them and are of minimal distance apart. One of the lines must contain an edge $ab$ of the convex hull, and the other line must go through a point c of the convex hull such that (a,c) and (b,c) are antipodal pairs. ab and c are referred to as an antipodal edge-vertex pair. Consider the dual of the point set. The points dualize to lines and the convex hull of the points dualizes to the upper and lower envelope of the set of lines. The vertices of the upper convex hull dualize to segments on the upper envelope. The vertices of the lower convex hull dualize to segments on the lower envelope. The range of slopes of the supporting lines of a point on the hull dualize to the x-interval of segment that point dualizes to. When viewed in this dualized fashion the antipodal pairs, are pairs of segments, one from the upper envelope, one from the lower, with overlapping x ranges. Now, the upper and lower envelopes can be viewed as two different x-ordered lists of non overlapping intervals. If these two lists are merged, the antipodal pairs are the overlaps in the merged list. If a pair $ab$ and c is an antipodal edge-vertex pair, then the x-interval for a and b must both intersect the x-interval for c. This means that the common endpoint of the x intervals for a and b must lie within the x-interval for c. The endpoints of both of the sets of x-intervals can be maintained in a kinetic sorted list. When points swap, the list of antipodal edge-point pairs are updated appropriately. The upper and lower envelopes can be maintained using the standard data structure for kinetic convex hull. The minimum distance between edge-point pairs can be maintained with a kinetic tournament. Thus, using kinetic convex hull to maintain the upper and lower envelopes, a kinetic sorted list on these intervals to maintain the antipodal edge-vertex pairs, and a kinetic tournament to maintain the pair of minimum distance apart, the diameter of a moving point set can be maintained. This data structure is responsive, compact and efficient. The data structure uses $O(n)$ space because the kinetic convex hull, sorted list, and tournament data structures all use $O(n)$ space. In all of the data structures, events, inserts, and deletes can be handled in $O(\backslash log^2\; n)$ time, so the data structure are responsive, requiring $O(\backslash log^2\; n)$ per event. The data structure is efficient because the total number of events is $O(n^)$ for all $\backslash epsilon>0$ and the width of a point set can change $\backslash Omega(n^2)$ times, even if the points are moving linearly. This data structure is not local because one point may be in many antipodal edge-vertex pairs, and thus appear many times in the kinetic tournament. The existence of a local kinetic data structure for width is open. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Kinetic width」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.